SP1026 FAVDICE - Favorite Dice

dp[i]dp[i] 表示当前已经得到了 ii 个面后的期望次数。
有两种情况:

1.掷出已有的面,概率为 in\frac{i}{n}

2.掷出新的面 , 概率为 nin\frac{n-i}{n}

那么有:

f[i]=inf[i]+ninf[i+1]+1f[i]=\frac{i}{n}f[i]+\frac{n-i}{n}f[i+1]+1

ninf[i]=ninf[i+1]+1\frac{n-i}{n}f[i]=\frac{n-i}{n}f[i+1]+1

f[i]=f[i+1]+nnif[i]=f[i+1]+\frac{n}{n-i}

边界条件 f[n]=0f[n]=0 , 倒推即可。

当然,把上式暴力展开后发现答案为 ni=1n1in\sum_{i=1}^n\frac{1}{i}

这其实是一个调和级数,由于精度要求不高 n>50n > 50 可用公式解决。

#include <cmath>
#include <cstdio>

const double Gamma = 0.577215664901532860606512090082402431042159335;
const int MAXN = 1000;
int t , n;
double Ans;

int main( ) {
	scanf("%d",&t);
	while( t -- ) {
		scanf("%d",&n);
        
        Ans = 0;
        if( n <= 50 )
		    for( int i = 1 ; i <= n ; i ++ ) Ans += 1.0 / i;
        else
            Ans = log( n ) + Gamma + 1.0 / 2 / n;
		printf("%.2f\n", Ans * n );
	}
	return 0;
}